package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;
import cn.pugle.oj.catalog.GraphProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/surrounded-regions/
 * flood洪水算法
 *
 * @author tzp
 * @since 2020/11/2
 */
public class LC130_1 implements Backtracking, GraphProblem {
    int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    class Pair<A, B> {
        A a;
        B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }
    }

    public void solve(char[][] board) {
        if (board == null || board.length <= 1) return;
        boolean[][] visited = new boolean[board.length][board[0].length];
        ArrayList<Pair<Integer, Integer>> path = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    path.clear();
                    if (dfs(board, i, j, visited, path)) {
                        for (Pair<Integer, Integer> p : path) {
                            board[p.a][p.b] = 'X';
                        }
                    }
                }
            }
        }
    }

    //深度优先为O的格子, flood过去所有相连的O, 返回算法需要flip
    //记录visited, 不reset, 所以不是回溯
    public boolean dfs(char[][] board, int i, int j,
                       boolean[][] visited, List<Pair<Integer, Integer>> path) {
        visited[i][j] = true;
        path.add(new Pair<>(i, j));
        boolean valid = true;
        for (int k = 0; k < directions.length; k++) {
            int newI = i + directions[k][0];
            int newJ = j + directions[k][1];
            if (!inArea(board, newI, newJ)) {
                valid = false;
            } else if (!visited[newI][newJ] && board[newI][newJ] == 'O') {
                valid = dfs(board, newI, newJ, visited, path) && valid;
            }
        }
        return valid;
    }

    public boolean inArea(char[][] board, int i, int j) {
        return i >= 0 && j >= 0 && i < board.length && j < board[0].length;
    }

    public static void main(String[] args) {
//        char[][] a = {
//                {'X', 'X', 'X', 'X'},
//                {'X', 'O', 'O', 'X'},
//                {'X', 'X', 'O', 'X'},
//                {'X', 'O', 'X', 'X'}};
        char[][] a = {
                {'O', 'O', 'O', 'O', 'X', 'X'},
                {'O', 'O', 'O', 'O', 'O', 'O'},
                {'O', 'X', 'O', 'X', 'O', 'O'},
                {'O', 'X', 'O', 'O', 'X', 'O'},
                {'O', 'X', 'O', 'X', 'O', 'O'},
                {'O', 'X', 'O', 'O', 'O', 'O'}};
        new LC130_1().solve(a);
        System.out.println(Arrays.deepToString(a));
    }
}
